package com.leetcode;

import java.util.*;

/**
 * 310. 最小高度树
 * 广度优先遍历图, 找出最长路径
 * 广度优先遍历最后遍历的节点是离当前节点层次最深的节点
 *
 * @author fy
 * @date 2022/4/6 21:21
 */
public class Solution310 {

    private List<Integer>[] adj;
    private int v;
    private int e;

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();
        if (n <= 0) {
            return res;
        }
        if (n == 1) {
            res.add(0);
            return res;
        }
        if (n == 2) {
            res.add(0);
            res.add(1);
            return res;
        }
        this.v = n;
        this.e = edges.length;

        this.initAdj(edges);

        // 进行一次广度优先遍历
        // 初始化 路径数组
        int[] from = new int[this.v];
        Arrays.fill(from, -1);
        // 找到与节点 0 最远的节点 x
        int x = bfs(0, from);
        // 找到与节点 x 最远的节点 y
        Arrays.fill(from, -1);
        int y = bfs(x, from);

        // 找到x 到 y 的路径, 该路径为最长路径
        // 只需要从该最长路径上找中间点作为根节点则树的高度最低
        List<Integer> path = new ArrayList<>();
        int parent = y;
        while (parent != -1) {
            path.add(parent);
            parent = from[parent];
        }

        // 如果是偶数个节点, 则中间节点有两个, 如果是奇数则只有一个
        int h = path.size();
        if (h % 2 == 0) {
            res.add(path.get(h / 2 - 1));
        }
        res.add(path.get(h / 2));
        return res;
    }

    private void initAdj(int[][] edges) {
        // 初始化邻接表
        adj = new List[this.v];
        for (int i = 0; i < this.v; i++) {
            adj[i] = new ArrayList<>();
        }

        // 将边信息转换存储到邻接表
        for (int i = 0; i < this.e; i++) {
            int[] edge = edges[i];
            // 因为是无向图, 需要存对应双向的路径
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }
    }

    private int bfs(int node, int[] from) {
        // 遍历的节点之前是否已经访问过
        boolean[] visited = new boolean[this.v];
        // 队列保存待遍历的节点
        Queue<Integer> queue = new ArrayDeque<>();
        // 首先将起始节点推入队列中, 并设置为已访问
        queue.offer(node);
        visited[node] = true;
        // 设置初始节点 来自的节点为 -1
        // 上一次出队列的节点
        int lastNode = -1;
        from[node] = lastNode;

        while (!queue.isEmpty()) {
            lastNode = queue.poll();
            // 拿出队首元素 依次将与其连接的节点推入队列
            for (Integer newNode : adj[lastNode]) {
                // 如果没有访问过则推入队列等待访问
                if (!visited[newNode]) {
                    visited[newNode] = true;
                    from[newNode] = lastNode;
                    queue.offer(newNode);
                }
            }
        }
        // 将最后遍历的元素返回
        return lastNode;
    }

}
